package com.wide.core.shared.collection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

import com.wide.core.shared.json.JsonObject;
import com.wide.core.shared.json.JsonSerializable;
import com.wide.core.shared.json.JsonString;
import com.wide.core.shared.json.JsonValue;

public abstract class JsonCSTrie<K extends Comparable<K>, V> implements Map<K, V>, JsonSerializable<JsonObject>, Comparable<JsonCSTrie<K,V>> {
	private final K prefix;
	private final Set<JsonCSTrie<K,V>> children = new TreeSet<JsonCSTrie<K,V>>();
	
	private V value = null;
	private int size = 0;

	public JsonCSTrie(K prefix) {
		super();
		this.prefix = prefix;
	}

	@Override
	public JsonObject toJson() {
		JsonObject json = new JsonObject();
		json.put("__type", new JsonString("JsonCSTrie"));
		if (value != null) {
			json.put("__value", getValueJson());
		}
		
		for (JsonCSTrie<K,V> child : children) {
			json.put(getPrefixJson(), child.toJson());
		}
		
		return json;
	}

	@Override
	public void fromJson(JsonValue obj) {
		if (obj.isObject()) {
			JsonObject jsonObj = (JsonObject)obj;
			if (jsonObj.containsKey("__type") && jsonObj.get("__type").toString().equals("JsonCSTrie")) {
				if (jsonObj.containsKey("__value")) {
					this.value = valueFromJson(jsonObj.get("__value"));
				}
				
				for (String key : jsonObj.keySet()) {
					if (key.equals("__type") || key.equals("__value")) {
						continue;
					}
					
					K prefix = prefixFromJson(key);
					JsonCSTrie<K,V> child = createChild(prefix);
					this.children.add(child);
					child.fromJson(jsonObj.get(key));
				}
			} else {
				this.value = valueFromJson(jsonObj);
			}
		} else {
			this.value = valueFromJson(obj);
		}
	}

	@Override
	public void clear() {
		this.value = null;
		for (JsonCSTrie<K,V> child : children) {
			child.clear();
		}
		children.clear();
	}

	@SuppressWarnings("unchecked")
	@Override
	public boolean containsKey(Object key) {
		K keyObj = null;
		try {
			keyObj = (K)key;
		} catch (Exception e) {
			return false;
		}
		if (keyObj == null) {
			return this.value != null;
		} else {
			for (JsonCSTrie<K,V> child : children) {
				K commonPrefix = getCommonPrefix(keyObj, child.prefix);
				if (commonPrefix != null) {
					K keyTail = getKeyTail(commonPrefix, keyObj);
					return child.containsKey(keyTail);
				}
			}
			
			return false;
		}
	}

	@Override
	public boolean containsValue(Object value) {
		if (this.value == value) {
			return true;
		} else {
			for (JsonCSTrie<K,V> child : children) {
				if (child.containsValue(value)) {
					return true;
				}
			}
			return false;
		}
	}

	@Override
	public Set<java.util.Map.Entry<K, V>> entrySet() {
		return null;
	}

	@SuppressWarnings("unchecked")
	@Override
	public V get(Object key) {
		K keyObj = null;
		try {
			keyObj = (K)key;
		} catch (Exception e) {
			return null;
		}
		if (keyObj == null) {
			return this.value;
		} else {
			for (JsonCSTrie<K,V> child : children) {
				K commonPrefix = getCommonPrefix(keyObj, child.prefix);
				if (commonPrefix != null) {
					K keyTail = getKeyTail(commonPrefix, keyObj);
					return child.get(keyTail);
				}
			}
			
			return null;
		}
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public Set<K> keySet() {
		Set<K> keys = new TreeSet<K>();
		if (value != null) {
			keys.add(prefix);
			for (JsonCSTrie<K,V> child : children) {
				for (K key : child.keySet()) {
					keys.add(getFullKey(prefix, key));
				}
			}
		}
		return keys;
	}

	@Override
	public V put(K key, V value) {
		if (putHelper(key, value)) {
			size++;
		}
		return value;
	}
	
	private boolean putHelper(K key, V value) {
		if (value == null) {
			return false;
		}
		if (key == null) {
			boolean isNewValue = this.value == null;
			this.value = value;
			return isNewValue;
		} else {
			for (JsonCSTrie<K,V> child : children) {
				K commonPrefix = getCommonPrefix(key, child.prefix);
				if (commonPrefix.compareTo(child.prefix) == 0) {
					K keyTail = getKeyTail(commonPrefix, key);
					boolean isNewValue = child.putHelper(keyTail, value);
					if (isNewValue) {
						size++;
					}
					
					return isNewValue;
				}
			}
			
			JsonCSTrie<K,V> newChild = createChild(key);
			children.add(newChild);
			
			boolean isNewValue = newChild.putHelper(key, value);
			if (isNewValue) {
				size++;
			}
			
			return isNewValue;
		}
	}

	@Override
	public void putAll(Map<? extends K, ? extends V> m) {
		for (K key : m.keySet()) {
			this.put(key, m.get(key));
		}
	}

	@SuppressWarnings("unchecked")
	@Override
	public V remove(Object key) {
		K keyObj = null;
		try {
			keyObj = (K)key;
		} catch (Exception e) {
			return null;
		}
		if (key == null) {
			V value = this.value;
			this.value = null;
			
			if (value != null) {
				size--;
			}
			return value;
		} else {
			V value = null;
			JsonCSTrie<K,V> childWithValue = null;
			for (JsonCSTrie<K,V> child : children) {
				K commonPrefix = getCommonPrefix(keyObj, child.prefix);
				if (commonPrefix != null) {
					K keyTail = getKeyTail(commonPrefix, keyObj);
					value = child.remove(keyTail);
					childWithValue = child;
					break;
				}
			}
			
			if (value != null) {
				size--;
				if (childWithValue.value == null) {
					if (childWithValue.children.size() == 0) {
						this.children.remove(childWithValue);
					} else if (childWithValue.children.size() == 1) {
						K childPrefix = null;
						V childValue = null;
						for (JsonCSTrie<K,V> child : childWithValue.children) {
							childPrefix = child.prefix;
							childValue = child.value;
						}
						JsonCSTrie<K,V> newChild = createChild(getFullKey(childWithValue.prefix, childPrefix));
						newChild.value = childValue;
						
						childWithValue.clear();
						this.children.remove(childWithValue);
						this.children.add(newChild);
					}
				}
			}
			return value;
		}
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Collection<V> values() {
		List<V> values = new ArrayList<V>();
		if (value != null) {
			values.add(value);
		}
		
		for (JsonCSTrie<K,V> child : children) {
			values.addAll(child.values());
		}
		
		return values;
	}

	@Override
	public int compareTo(JsonCSTrie<K, V> o) {
		if (o == null) {
			return -1;
		} else {
			return this.prefix.compareTo(o.prefix);
		}
	}
	
	/**
	 * Compare two keys together to find a common prefix.
	 * @param key1
	 * @param key2
	 * @return The prefix that the keys share in common or null if none exists.
	 */
	protected abstract K getCommonPrefix(K key1, K key2);
	
	/**
	 * Given a prefix, retrieve the rest of the key.
	 * @param prefix
	 * @param key
	 * @return The rest of the key, or null if there is no more.
	 */
	protected abstract K getKeyTail(K prefix, K key);
	
	/**
	 * Given a prefix and a tail, reconstruct the full key.
	 * @param prefix
	 * @param tail
	 * @return The full key.
	 */
	protected abstract K getFullKey(K prefix, K tail);
	
	/**
	 * Create a new JsonCSTrie object with the given prefix. This method is necessary
	 * to make sure that the correct instantiating class of the JsonCSTrie is being used
	 * at all times.
	 * @param prefix
	 * @return A new JsonCSTrie with the given prefix.
	 */
	protected abstract JsonCSTrie<K,V> createChild(K prefix);
	
	/**
	 * Gets the string value of the prefix to be used in a JsonObject
	 * @return The string value of the Prefix.
	 */
	protected abstract String getPrefixJson();
	
	/**
	 * Gets the JsonValue of the value in the Trie.
	 * @return The JsonValue of the value in the Trie.
	 */
	protected abstract JsonValue getValueJson();
	
	/**
	 * Create a prefix from a String value in Json.
	 * @param key The String key used in the Json.
	 * @return The prefix that was created.
	 */
	protected abstract K prefixFromJson(String key);
	
	/**
	 * Create a value from a Json object.
	 * @param value The Json object to process.
	 * @return The value object created.
	 */
	protected abstract V valueFromJson(JsonValue value);
}
